package Busquedas;

import Problemas.Principal;
import Problemas.Problema;
import java.util.ArrayList;

/**
 * Clase para implementar la busqueda heuristica de A*.
 */
public class AEstrella extends Busqueda{


    protected ArrayList<Nodo> cerrados;
    /**
	 Hereda de la clase problema,introducimos un parametro cerrados para llevar los nodos cerrados
	 */
	public AEstrella(Problema p) {
		super(p);
        cerrados=new ArrayList<Nodo>();
	}


       @Override
	public ArrayList<Estado> buscar(boolean controlCiclos) {
		long tiempo1=System.currentTimeMillis();
		Nodo nodo = this.getNodo();
		Nodo hijo;
        nodo.setCosteAcumulado(0);
		nodo.setValorHeuristico(this.getProblema().funcionHeuristica(nodo.getEstado()));
        abiertos.add(nodo);//aÃ±adir aki??
		try{
			while (!this.getProblema().estadoFinal(nodo.getEstado())&& !(abiertos.isEmpty())){
                abiertos.remove(indiceMejor());
				for (int op = 0; op < this.getProblema().getnumOper(); op++){
					if (nodo.getOperadoresAplicados()[op]!=1){
						Estado e = this.getProblema().aplicaOperador(nodo.getEstado(),op);
						if (e != null ){
                            Nodo aux=new Nodo(e,nodo.getNumMaxHijos(),op);
                            aux.setCosteAcumulado(nodo.getCosteAcumulado()+this.getProblema().getCosteOperador(op));//El coste es el del operador mas el que lleva el padre
							aux.setValorHeuristico(this.getProblema().funcionHeuristica(aux.getEstado()));
                            aux.setPadre(nodo);
                            if(this.estaEnAbiertos(aux)){
                                Nodo abierto=this.dameElAbierto(aux);
                                if((aux.getCosteAcumulado())<(abierto.getCosteAcumulado())){//Esta en abiertos
                                    hijo = nodo.anadeHijo(op,e,this.getProblema().getCosteOperador(op));
                                    hijo.setValorHeuristico(this.getProblema().funcionHeuristica(hijo.getEstado()));
                                    int indiceAbierto=this.dameindiceAbierto(aux);
                                    abiertos.set(indiceAbierto, hijo);
                                }
                            }
                            else{
                                if(this.estaEnCerrados(aux)){//Ha sido cerrado anteriormente
                                        if((aux.getCosteAcumulado())<(this.dameElCerrado(aux).getCosteAcumulado())){
                                            hijo = nodo.anadeHijo(op,e,this.getProblema().getCosteOperador(op));
                                            hijo.setValorHeuristico(this.getProblema().funcionHeuristica(hijo.getEstado()));
                                            int indice=this.dameIndiceCerrado(aux);
                                            int diferencia=this.cerrados.get(indice).getCosteAcumulado()-aux.getCosteAcumulado();
                                            hijo.setHijos(this.cerrados.get(indice).getHijos());
                                            actulizaNodosCerrados(diferencia,hijo);
                                        }
                                    }
                                    else{//no esta ni en abiertos ni en expandidos
                                        hijo = nodo.anadeHijo(op,e,this.getProblema().getCosteOperador(op));
                                        hijo.setValorHeuristico(this.getProblema().funcionHeuristica(hijo.getEstado()));
                                        abiertos.add(hijo);
                                    }
                                }

						}
					}
				}
                if(!abiertos.isEmpty()){
                    cerrados.add(nodo);
                    nodo = abiertos.get(indiceMejor());
                    contadorNodos++;
                }
                else
                    return null;
				if (contadorNodos>maxContadorNodos) return null;
			}
		//	this.dibujaNodos(nodo.getNumMaxHijos(),nodo,nodo.getEstado());
			this.generaCamino(nodo);
			long tiempo2=System.currentTimeMillis();
			this.setTiempoTotal((tiempo2-tiempo1));
			return camino;
		}
            catch(OutOfMemoryError e){
			System.out.println(abiertos.size());
			abiertos = null;
			return null;
		}
	}



	/**
	 * Metodo que devuelve el indice con mejor coste(coste real+coste heuristico)
	 */
	public int indiceMejor(){
		int indiceMejor = 0;
		int i = 0;
		int menorValor = (abiertos.get(0).getValorHeuristico()+abiertos.get(0).getCosteAcumulado());
		while (i < abiertos.size()){
			if (menorValor > (abiertos.get(i).getValorHeuristico()+abiertos.get(i).getCosteAcumulado())){
				indiceMejor = i;
				menorValor = (abiertos.get(i).getValorHeuristico()+abiertos.get(i).getCosteAcumulado());
			}else{
				i++;
			}
		}
		return indiceMejor;
	}


	/**
	 * Metodo que devuelve cierto si el nodo esta entre los nodos abiertos
	 */
	protected boolean estaEnAbiertos(Nodo n){
		boolean encontrado=false;
		int i=0;
		while (!encontrado && (i<abiertos.size())){
			if (n.getEstado().esIgual(abiertos.get(i).getEstado())){
				encontrado=true;
			}
			else i++;
		}
		return encontrado;
	}
    	public Nodo dameElAbierto(Nodo n){
		int i=0;
		while ((i<abiertos.size())){
			if (n.getEstado().esIgual(abiertos.get(i).getEstado())){
				return abiertos.get(i);
			}
			else i++;
		}
		return n;
	}
   public int dameindiceAbierto(Nodo n){
		int i=0;
		while ((i<abiertos.size())){
			if (n.getEstado().esIgual(abiertos.get(i).getEstado())){
				return i;
			}
			else i++;
		}
		return -1;
	}
   	/**
	 * Metodo que devuelve cierto si el nodo esta entre los nodos cerrados
	 */
    	protected boolean estaEnCerrados(Nodo n){
		boolean encontrado=false;
		int i=0;
		while (!encontrado && (i<cerrados.size())){
			if (n.getEstado().esIgual(cerrados.get(i).getEstado())){
				encontrado=true;
			}
			else i++;
		}
		return encontrado;
	}
    	public Nodo dameElCerrado(Nodo n){
		int i=0;
		while ((i<abiertos.size())){
			if (n.getEstado().esIgual(cerrados.get(i).getEstado())){
				return cerrados.get(i);
			}
			else i++;
		}
		return n;
	}
   public int dameIndiceCerrado(Nodo n){
		int i=0;
		while ((i<abiertos.size())){
			if (n.getEstado().esIgual(cerrados.get(i).getEstado())){
				return i;
			}
			else i++;
		}
		return -1;
	}

	/**
	 * Metodo que actuliza los hijos de un nodo del cual se ha encontrado un camino mejor
	 */
    private void actulizaNodosCerrados(int diferencia,Nodo actualizar) {
        int indice=this.dameIndiceCerrado(actualizar);
        for(int i=0;i<this.cerrados.get(indice).getNumHijos();i++){
            if(this.estaEnAbiertos(this.cerrados.get(indice).getHijos(i))){
                int ind=this.dameindiceAbierto(this.cerrados.get(indice).getHijos(i));
                this.abiertos.get(ind).setCosteAcumulado(this.abiertos.get(ind).getCosteAcumulado()-diferencia);
                this.abiertos.get(ind).setPadre(actualizar.getPadre());
                actulizaNodosCerrados(diferencia,this.abiertos.get(ind));
            }
            if(this.estaEnCerrados(this.cerrados.get(indice).getHijos(i))){
                int ind=this.dameIndiceCerrado(this.cerrados.get(indice).getHijos(i));
                this.cerrados.get(ind).setCosteAcumulado(this.cerrados.get(ind).getCosteAcumulado()-diferencia);
                this.cerrados.get(ind).setPadre(actualizar.getPadre());
                actulizaNodosCerrados(diferencia,this.cerrados.get(ind));
            }
        }
    }
}